def insertion_sort(arr):
    """
    插入排序函数实现
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    # 遍历从1到n的所有元素
    for i in range(1, len(arr)):
        # 将当前元素存储在一个临时变量中
        key = arr[i]
        # 当前元素的索引初始化为i
        j = i - 1
        # 如果当前元素小于前面的元素，则向左移动较大的元素
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # 将key（即当前元素）放在正确的位置
        arr[j + 1] = key

# 示例
arr_example = [0, 1, 17, 7, 9, 3, 18, 25, 8]
insertion_sort(arr_example)
print("Sorted array:", arr_example)  # 输出：[0, 1, 3, 7, 8, 9, 17, 18, 25]12